package apiDemo.arrayAdvance;

import java.util.Arrays;

/**
 * 快排
 * 
 * 在一次递归中找到基准数的位置
 */

public class Demo02 {
  public static void main(String[] args) {
    int[] arr = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
    quiteSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
  }

  private static void quiteSort(int[] arr, int left, int right) {
    if (right < left) {
      return;
    }
    int left0 = left;
    int right0 = right;

    int baseNumber = arr[left0];
    while (left != right) {
      while (arr[right] >= baseNumber && right > left) {
        right--;
      }
      while (arr[left] <= baseNumber && right > left) {
        left++;
      }
      // 交换两个值的位置
      int temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
    }
    // 基准数归位
    int temp = arr[left];
    arr[left] = arr[left0];
    arr[left0] = temp;

    quiteSort(arr, left0, left - 1);
    quiteSort(arr, left + 1, right0);
  }

}
